package hotLeetcode;

public class H142Leetcode {
    public ListNode detectCycle(ListNode head) {
        //判断是否有环
        ListNode fast = head;
        ListNode slow = head;
        while ( fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) { // 说明有环
                ListNode index1 = head;
                ListNode index2 = fast;

//                if (index1 == index2) {
//                    return index2;
//                } else {
//                    index1 = index1.next;
//                    index2 = index2.next.next;
//                }
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;

            }

        }

        return null;

    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
